package com.zql.LeetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * Created By ShuHua on 2021/10/19.
 */
public class CheckInclusion_567 {
    public static boolean checkInclusion(String s1, String s2) {
        Map<Character,Integer> need = new HashMap<Character, Integer>();
        Map<Character,Integer> window = new HashMap<Character, Integer>();

        for(char c:s1.toCharArray()){
           need.put(c,need.getOrDefault(c,0)+1);

        }

        int right=0;
        int valid=0;
        int left=0;
        char[] c2 = s2.toCharArray();
        while (right<c2.length){
            char c = c2[right];
            right++;

            window.put(c,window.getOrDefault(c,0)+1);
            if(need.containsKey(c)){
                if(window.get(c).equals(need.get(c)))
                    valid++;
            }
            while(valid==need.size()){
                //如果仅仅是前面俩个条件，当碰到s1="hello"，s2="ooolleoooleh"
                // 这种情况right=13的时候前俩个条件已满足，但是此时window内的字符数量远大于need
                if(valid==need.size()&&need.size()==window.size()&&right-left==s1.length())
                    return true;
                char c1 = c2[left];
                left++;
                if(window.get(c1)>1){
                    window.put(c1,window.get(c1)-1);
                }else {
                    window.remove(c1);
                }
                if(need.containsKey(c1)){
                    if ((window.containsKey(c1)&&window.get(c1)<need.get(c1))|| !window.containsKey(c1))
                        valid--;
                }
            }
        }
        return false;
    }
    public static boolean checkInclusion2(String s1, String s2) {
        Map<Character, Integer> need = new HashMap<Character, Integer>();
        Map<Character, Integer> window = new HashMap<Character, Integer>();

        for (char c : s1.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int right = 0;
        int valid = 0;
        int left = 0;
        char[] c2 = s2.toCharArray();
        while (right < c2.length) {
            char c = c2[right];
            right++;
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(need.get(c).equals(window.get(c)))
                    valid++;
            }

            while(right-left>=s1.length()){

                if(valid==need.size())return true;
                char c1 = c2[left];
                left++;
                if(need.containsKey(c1)){
                    if(window.get(c1).equals(need.get(c1)))
                        valid--;
                    window.put(c1,window.get(c1)-1);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        String s1 = "hello";
        String s2 = "ooolleoooleh";
        boolean b = checkInclusion2(s1,s2);
        System.out.println(b);
    }
}
